GermanWikipedia - /page/entry.mu

<!DOCTYPE html>

<title>Perfekter Code</title>

</head>

<h1 id="firstHeading" class="firstHeading mw-first-heading">Perfekter Code</h1>

</header>

</div>

<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="de" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="de" dir="ltr">Ein perfekter Code, oder auch dicht gepackter Code, bezeichnet in der <a href="Codierungstheorie" class="mw-redirect" title="Codierungstheorie">Codierungstheorie</a> einen <a href="Blockcode" title="Blockcode">Blockcode</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {C}}\subset \Sigma ^{n}}">

</mrow>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {C}}\subset \Sigma ^{n}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ebe335a7ad2616975b13db3b6cc67176fce5f4ae.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:7.234ex; height:2.343ex;" alt="{\displaystyle {\mathcal {C}}\subset \Sigma ^{n}}" loading="lazy">, in dem jedes Wort <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w\in \Sigma ^{n}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w\in \Sigma ^{n}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2ef0581e4f7d507bcf8bc6593ccade369898bcec.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:7.401ex; height:2.343ex;" alt="{\displaystyle w\in \Sigma ^{n}}" loading="lazy"> nur zu genau einem <a href="Code" title="Code">Codewort</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c\in {\mathcal {C}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c\in {\mathcal {C}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/6d67240ce3f564bd39e61e340509abe02b0373f6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.087ex; height:2.176ex;" alt="{\displaystyle c\in {\mathcal {C}}}" loading="lazy"> (und nicht zu mehreren) einen geringsten <a href="Hamming-Abstand" title="Hamming-Abstand">Hamming-Abstand</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d_{w}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d_{w}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e8f34228ad0512bbf60d8a8c4e3a31ae32ac108c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.618ex; height:2.509ex;" alt="{\displaystyle d_{w}}" loading="lazy"> hat, wobei <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d_{w}\leq \Delta ({\mathcal {C}})}">

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d_{w}\leq \Delta ({\mathcal {C}})}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/80327f700fc3ec4af49c843f4a252bc29e5e6be2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.701ex; height:2.843ex;" alt="{\displaystyle d_{w}\leq \Delta ({\mathcal {C}})}" loading="lazy"> ist.

Bei der meist verwendeten <a href="Decodierregel#Maximum-Likelihood-Decodierung" title="Decodierregel">Maximum-Likelihood-Decodierung</a> bedeutet dies, dass jedes empfangene Wort <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/88b1e0c8e1be5ebe69d18a8010676fa42d7961e6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.664ex; height:1.676ex;" alt="{\displaystyle w}" loading="lazy"> genau ein Codewort <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/86a67b81c2de995bd608d5b2df50cd8cd7d92455.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.007ex; height:1.676ex;" alt="{\displaystyle c}" loading="lazy"> hat, zu dem es den geringsten Hamming-Abstand hat und zu dem es eindeutig zugeordnet werden kann. Daraus leitet sich die Bezeichnung perfekt ab, denn es gibt keine mehrdeutigen Decodiermöglichkeiten.

<div class="mw-heading mw-heading2"><h2 id="Mathematische_Beschreibung">Mathematische Beschreibung</h2></div>

Sei <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {C}}\subset \Sigma ^{n}}">

</mrow>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {C}}\subset \Sigma ^{n}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ebe335a7ad2616975b13db3b6cc67176fce5f4ae.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:7.234ex; height:2.343ex;" alt="{\displaystyle {\mathcal {C}}\subset \Sigma ^{n}}" loading="lazy"> ein <a href="Blockcode" title="Blockcode">Blockcode</a> mit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |\Sigma |=q}">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |\Sigma |=q}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0abd464fb116fdb3e3fb42d83a9a65ca3b982c18.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.14ex; height:2.843ex;" alt="{\displaystyle |\Sigma |=q}" loading="lazy">, wobei <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Sigma }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Sigma }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/9e1f558f53cda207614abdf90162266c70bc5c1e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.678ex; height:2.176ex;" alt="{\displaystyle \Sigma }" loading="lazy"> das verwendete <a href="Alphabet_(Mathematik)" class="mw-redirect" title="Alphabet (Mathematik)">Alphabet</a> darstellt. Alle Codeworte <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {C}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {C}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e7b3edab7022ca9e2976651bc59c489513ee9019.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.239ex; height:2.176ex;" alt="{\displaystyle {\mathcal {C}}}" loading="lazy"> haben untereinander einen Mindest-Hamming-Abstand von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e85ff03cbe0c7341af6b982e47e9f90d235c66ab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.216ex; height:2.176ex;" alt="{\displaystyle d}" loading="lazy">. Der Blockcode kann damit

<mrow>

<mfrac>

<mrow>

</mrow>

</mfrac>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t=\left\lfloor {\frac {d-1}{2}}\right\rfloor }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/715615f7baa26e6b19635a0f9865ef76fbe99b0c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:12.703ex; height:6.176ex;" alt="{\displaystyle t=\left\lfloor {\frac {d-1}{2}}\right\rfloor }" loading="lazy"></dd></dl>

Fehler korrigieren.

Um perfekt zu sein, muss der minimale Hamming-Abstand zwischen zwei Codeworten eines Codes ungerade sein, da sonst für <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c_{1},c_{2}\in {\mathcal {C}}:\Delta (c_{1},c_{2})=d}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c_{1},c_{2}\in {\mathcal {C}}:\Delta (c_{1},c_{2})=d}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/72b95a92b4250d1375c3737ada31b6a8fbb76832.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:24.389ex; height:2.843ex;" alt="{\displaystyle c_{1},c_{2}\in {\mathcal {C}}:\Delta (c_{1},c_{2})=d}" loading="lazy"> mindestens ein Wort <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/88b1e0c8e1be5ebe69d18a8010676fa42d7961e6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.664ex; height:1.676ex;" alt="{\displaystyle w}" loading="lazy"> mit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Delta (c_{1},w)={\tfrac {d}{2}}=\Delta (w,c_{2})}">

<msub>

</mrow>

</msub>

<mfrac>

</mfrac>

</mstyle>

</mrow>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Delta (c_{1},w)={\tfrac {d}{2}}=\Delta (w,c_{2})}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c22481886e92334ed7d07cd3abff6b929264247d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:24.901ex; height:3.676ex;" alt="{\displaystyle \Delta (c_{1},w)={\tfrac {d}{2}}=\Delta (w,c_{2})}" loading="lazy"> existiert, was im Widerspruch zur Definition perfekter Codes steht.

Da der Code <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/65658b7b223af9e1acc877d848888ecdb4466560.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.84ex; height:2.009ex;" alt="{\displaystyle t}" loading="lazy">-fehlerkorrigierend ist, kann ein Wort <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w\in \Sigma ^{n}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w\in \Sigma ^{n}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2ef0581e4f7d507bcf8bc6593ccade369898bcec.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:7.401ex; height:2.343ex;" alt="{\displaystyle w\in \Sigma ^{n}}" loading="lazy"> einem Codewort <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c\in C}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c\in C}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/447d3982c94c23d6b6d01c90da81a6125aa26567.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.614ex; height:2.176ex;" alt="{\displaystyle c\in C}" loading="lazy"> eindeutig zugeordnet werden, wenn der Hamming-Abstand <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d=\Delta (c,w)\leq t}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d=\Delta (c,w)\leq t}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/1e3164a87bae8624ce1ceab5b5378c7cccb2c022.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:15.703ex; height:2.843ex;" alt="{\displaystyle d=\Delta (c,w)\leq t}" loading="lazy"> ist. Umgekehrt bedeutet dies für ein bestimmtes Codewort <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/86a67b81c2de995bd608d5b2df50cd8cd7d92455.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.007ex; height:1.676ex;" alt="{\displaystyle c}" loading="lazy">, dass alle Wörter <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/88b1e0c8e1be5ebe69d18a8010676fa42d7961e6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.664ex; height:1.676ex;" alt="{\displaystyle w}" loading="lazy"> mit einem Hamming-Abstand von maximal <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/65658b7b223af9e1acc877d848888ecdb4466560.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.84ex; height:2.009ex;" alt="{\displaystyle t}" loading="lazy"> nach <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/86a67b81c2de995bd608d5b2df50cd8cd7d92455.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.007ex; height:1.676ex;" alt="{\displaystyle c}" loading="lazy"> decodiert werden. Als Menge wird dies so geschrieben:

<msub>

</mrow>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {B}}_{t}(c):=\{w\in \Sigma ^{n}\mid \Delta (w,c)\leq t\}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/09d28dbc20724d892d7b24b8411159dcf8f6b350.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:31.966ex; height:2.843ex;" alt="{\displaystyle {\mathcal {B}}_{t}(c):=\{w\in \Sigma ^{n}\mid \Delta (w,c)\leq t\}}" loading="lazy"></dd></dl>

Diese Menge wird auch als Kugel (manchmal auch Hyperwürfel) mit Radius <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/65658b7b223af9e1acc877d848888ecdb4466560.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.84ex; height:2.009ex;" alt="{\displaystyle t}" loading="lazy"> um <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/86a67b81c2de995bd608d5b2df50cd8cd7d92455.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.007ex; height:1.676ex;" alt="{\displaystyle c}" loading="lazy"> bezeichnet. Die Anzahl der Elemente von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {B}}_{t}(c)}">

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {B}}_{t}(c)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/5c0a67b1d708834eb1e67b42025edb131ef6700f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.169ex; height:2.843ex;" alt="{\displaystyle {\mathcal {B}}_{t}(c)}" loading="lazy"> lässt sich berechnen zu:

</mrow>

<msub>

</mrow>

</mrow>

</msub>

</mrow>

</mrow>

</mrow>

</munderover>

<msup>

</mrow>

</msup>

<mrow>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |{\mathcal {B}}_{t}(c)|={\sum _{i=0}^{t}(q-1)^{i}{\binom {n}{i}}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/fa64a826650663e2bea0510ce6a3da19fa9d7aee.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:25.414ex; height:7.176ex;" alt="{\displaystyle |{\mathcal {B}}_{t}(c)|={\sum _{i=0}^{t}(q-1)^{i}{\binom {n}{i}}}}" loading="lazy"></dd></dl>

Für <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/add78d8608ad86e54951b8c8bd6c8d8416533d20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}" loading="lazy"> Fehlerstellen gibt es <a href="Binomialkoeffizient" title="Binomialkoeffizient"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/add78d8608ad86e54951b8c8bd6c8d8416533d20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}" loading="lazy"> aus <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"></a> mögliche Positionen für die Fehler. Dabei stehen pro Fehlerstelle <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle q-1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle q-1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/9bfc49678846b112cde021e3cb52d9b3b15decaf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:5.072ex; height:2.509ex;" alt="{\displaystyle q-1}" loading="lazy"> falsche Symbolwerte zur Verfügung. Es gibt <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |{\mathcal {C}}|}">

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |{\mathcal {C}}|}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/fdb08d532e1fc4ab01ec67f37082fef36f051caf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.533ex; height:2.843ex;" alt="{\displaystyle |{\mathcal {C}}|}" loading="lazy"> Kugeln. Diese sind disjunkte Teilmengen des <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Sigma ^{n}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Sigma ^{n}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e52398b6b9103472077e244c7db84eaeab4accdd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.897ex; height:2.343ex;" alt="{\displaystyle \Sigma ^{n}}" loading="lazy">. Daraus ergibt sich die Ungleichung

</mrow>

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</mrow>

</mrow>

</mrow>

</mrow>

</munderover>

<msup>

</mrow>

</msup>

<mrow>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |\Sigma ^{n}|\geq |{\mathcal {C}}|{\sum _{i=0}^{t}(q-1)^{i}{\binom {n}{i}}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/3c6e0e347d508a9bbd00923375051874655ca2dc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:25.674ex; height:7.176ex;" alt="{\displaystyle |\Sigma ^{n}|\geq |{\mathcal {C}}|{\sum _{i=0}^{t}(q-1)^{i}{\binom {n}{i}}}}" loading="lazy"></dd></dl>

Aufgelöst nach <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {C}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {C}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e7b3edab7022ca9e2976651bc59c489513ee9019.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.239ex; height:2.176ex;" alt="{\displaystyle {\mathcal {C}}}" loading="lazy"> und mit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |\Sigma ^{n}|=q^{n}}">

</mrow>

<msup>

</mrow>

</msup>

</mrow>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |\Sigma ^{n}|=q^{n}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f7ffc03e4d840d919202349ee758131021571273.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.587ex; height:2.843ex;" alt="{\displaystyle |\Sigma ^{n}|=q^{n}}" loading="lazy"> folgt:

</mrow>

</mrow>

</mrow>

<mfrac>

<msup>

</mrow>

</msup>

<mrow>

</mrow>

</mrow>

</munderover>

<msup>

</mrow>

</msup>

<mrow>

</mrow>

</mfrac>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |{\mathcal {C}}|\leq {\frac {q^{n}}{\sum _{i=0}^{t}(q-1)^{i}{\binom {n}{i}}}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e89eb9dcf144ef3bd4bf2ee76fa01e0f8a1375a6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.338ex; width:22.619ex; height:6.843ex;" alt="{\displaystyle |{\mathcal {C}}|\leq {\frac {q^{n}}{\sum _{i=0}^{t}(q-1)^{i}{\binom {n}{i}}}}}" loading="lazy"></dd></dl>

Diese Ungleichung für die Anzahl der Codewörter wird Hamming-Schranke oder auch Kugelpackungsschranke genannt.

Ein perfekter Code zeichnet sich dadurch aus, dass alle Wörter <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w\in \Sigma ^{n}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w\in \Sigma ^{n}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2ef0581e4f7d507bcf8bc6593ccade369898bcec.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:7.401ex; height:2.343ex;" alt="{\displaystyle w\in \Sigma ^{n}}" loading="lazy"> in genau einer der Kugeln enthalten sind (anders ausgedrückt: Die Kugeln überdecken den Raum). Deshalb gilt für die Hamming-Schranke selbst die Gleichheit.

<div class="mw-heading mw-heading2"><h2 id="Alternative_Interpretation">Alternative Interpretation</h2></div>

Man kann sich diese Grenze auch wie folgt veranschaulichen (der Einfachheit halber nur anhand binärer Codes erläutert, d. h. für <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle q=2}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle q=2}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/26622af6012fb982cab4e9584f57dd4f364233b7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:5.33ex; height:2.509ex;" alt="{\displaystyle q=2}" loading="lazy">):

Für einen <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/65658b7b223af9e1acc877d848888ecdb4466560.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.84ex; height:2.009ex;" alt="{\displaystyle t}" loading="lazy"> Fehler korrigierenden Code muss der Decoder genug

Information erhalten, um alle folgenden Fälle unterscheiden zu können:

</mrow>

</mrow>

</mrow>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |{\mathcal {C}}|=2^{k}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/1a91ad49d63c1197f639b65d307916250e39d17a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.882ex; height:3.176ex;" alt="{\displaystyle |{\mathcal {C}}|=2^{k}}" loading="lazy"> verschiedene Informationswörter und jeweils</li>

<li>alle möglichen Muster von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 0\ldots t}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 0\ldots t}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/59283f00d55925120a395c9b0f8b2b19a64cf977.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.5ex; height:2.176ex;" alt="{\displaystyle 0\ldots t}" loading="lazy"> Bitfehlern der <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> Bits eines Codewortes</li></ul>

Da es <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\binom {n}{i}}}">

<mrow>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\binom {n}{i}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/49fac0b85c8694b24e209bfe11dfeb4091aa116c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:4.816ex; height:6.176ex;" alt="{\displaystyle {\binom {n}{i}}}" loading="lazy"> Möglichkeiten gibt, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/add78d8608ad86e54951b8c8bd6c8d8416533d20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}" loading="lazy"> <a href="Bitfehler" title="Bitfehler">Bitfehler</a> auf

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> Bits zu verteilen, ergeben sich insgesamt

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</munderover>

<mrow>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2^{k}\cdot \sum _{i=0}^{t}{\binom {n}{i}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0c5d92f5a925983de675f7b75f1314845cbecf55.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:12.488ex; height:7.176ex;" alt="{\displaystyle 2^{k}\cdot \sum _{i=0}^{t}{\binom {n}{i}}}" loading="lazy"></dd></dl>

Fälle, die mit den zur Verfügung stehenden <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> Bits unterschieden werden müssen, also

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</munderover>

<mrow>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2^{n}\geq 2^{k}\cdot \sum _{i=0}^{t}{\binom {n}{i}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a01a6df03c40bda0b19a461756d42302556e6d58.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:17.968ex; height:7.176ex;" alt="{\displaystyle 2^{n}\geq 2^{k}\cdot \sum _{i=0}^{t}{\binom {n}{i}}}" loading="lazy">.</dd></dl>

Bei einem perfekten Code gilt Gleichheit, das heißt die <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> Bits tragen exakt die minimal benötigte Information. Diese (Un-)Gleichung entspricht der obigen allgemeinen Definition für den Fall <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle q=2}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle q=2}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/26622af6012fb982cab4e9584f57dd4f364233b7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:5.33ex; height:2.509ex;" alt="{\displaystyle q=2}" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |{\mathcal {C}}|=2^{k}}">

</mrow>

</mrow>

</mrow>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |{\mathcal {C}}|=2^{k}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/1a91ad49d63c1197f639b65d307916250e39d17a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.882ex; height:3.176ex;" alt="{\displaystyle |{\mathcal {C}}|=2^{k}}" loading="lazy">.

Man ist zwar eigentlich nur an der Korrektur der <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"> Informationsbits interessiert, wofür entsprechend weniger Zusatzinformation genügen würde – diese <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n-k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n-k}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b98e1d6a69bccd09a4b9b69bdf03a08c1706c8c1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.446ex; height:2.343ex;" alt="{\displaystyle n-k}" loading="lazy"> Bits Zusatzinformation müssten dann aber fehlerfrei sein, was natürlich in der Regel nicht gewährleistet ist. Daher ist eine Korrektur aller <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> Bits erforderlich.

<div class="mw-heading mw-heading2"><h2 id="Bekannte_Perfekte_Codes">Bekannte Perfekte Codes</h2></div>

Falls die Alphabetgröße <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle q}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle q}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/06809d64fa7c817ffc7e323f85997f783dbdf71d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.07ex; height:2.009ex;" alt="{\displaystyle q}" loading="lazy"> eine <a href="Primzahlpotenz" title="Primzahlpotenz">Primzahlpotenz</a> ist, so gilt:

Ist <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {C}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {C}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e7b3edab7022ca9e2976651bc59c489513ee9019.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.239ex; height:2.176ex;" alt="{\displaystyle {\mathcal {C}}}" loading="lazy"> ein perfekter Code mit Parametern <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle [n,k;d,q]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle [n,k;d,q]}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/3a9a0988ef325f77d93553b46afd8e3c52c07317.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.287ex; height:2.843ex;" alt="{\displaystyle [n,k;d,q]}" loading="lazy"> mit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k=\mathrm {log} _{q}(|{\mathcal {C}}|)}">

<msub>

</mrow>

</mrow>

</msub>

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k=\mathrm {log} _{q}(|{\mathcal {C}}|)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/954e08f9745f5c3b73f595fecd78b38e94209884.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:12.612ex; height:3.176ex;" alt="{\displaystyle k=\mathrm {log} _{q}(|{\mathcal {C}}|)}" loading="lazy">, so gibt es einen Code <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {D}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {D}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/3277962e1959c3241fb1b70c7f0ac6dcefebd966.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.792ex; height:2.176ex;" alt="{\displaystyle {\mathcal {D}}}" loading="lazy"> mit denselben Parametern, so dass <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {D}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {D}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/3277962e1959c3241fb1b70c7f0ac6dcefebd966.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.792ex; height:2.176ex;" alt="{\displaystyle {\mathcal {D}}}" loading="lazy"> einer der folgenden Codes ist<a href="#cite_note-1">[1]</a><a href="#cite_note-2">[2]</a>:

<ul><li>Ein trivialer Code: Ein Code heißt hier trivial,

<ul><li>falls er entweder nur <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle q^{0}=1}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle q^{0}=1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/1d89b73ca3c7955998c6a15df6ddfc72921001ff.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.395ex; height:3.009ex;" alt="{\displaystyle q^{0}=1}" loading="lazy">, d. h. ein einziges Codewort enthält: <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle [m,0;2m+1,q]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle [m,0;2m+1,q]}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/49a381f82f05aff81d9e1dc5ca8aae9d1892000e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:15.874ex; height:2.843ex;" alt="{\displaystyle [m,0;2m+1,q]}" loading="lazy"> oder</li>

<li>falls er alle <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle q^{m}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle q^{m}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/7b1c216190aa969e9cdcbf00c4db3cebe27486a8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.754ex; height:2.676ex;" alt="{\displaystyle q^{m}}" loading="lazy"> möglichen Codewörter der gegebenen Blocklänge enthält: <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle [m,m;1,q]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle [m,m;1,q]}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ad2e7286ea4b0a96ba426f71fe1634fcb28b8d75.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.708ex; height:2.843ex;" alt="{\displaystyle [m,m;1,q]}" loading="lazy">.</li></ul></li>

<li>Ein <a href="Dualsystem" title="Dualsystem">binärer</a> <a href="Wiederholungs-Code" class="mw-redirect" title="Wiederholungs-Code">Wiederholungs-Code</a> mit ungerader Codewortlänge. Die Parameter lauten <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle [2m+1,1;2m+1,2]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle [2m+1,1;2m+1,2]}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/be064dde6677d009578d239715b782e2498ad2fb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:21.132ex; height:2.843ex;" alt="{\displaystyle [2m+1,1;2m+1,2]}" loading="lazy">.</li>

<li>Ein <a href="Hamming-Code" title="Hamming-Code">Hamming-Code</a> über dem <a href="Endlicher_K%C3%B6rper" title="Endlicher Körper">endlichen Körper</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {F} _{q}}">

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {F} _{q}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/dbb96e056c071d13fc7702013f9273e7f5cd88a7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.409ex; height:2.843ex;" alt="{\displaystyle \mathbb {F} _{q}}" loading="lazy">, mit Parametern <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \;\left[{\frac {q^{m}-1}{q-1}},{\frac {q^{m}-1}{q-1}}-m;3,q\right]}">

<mrow>

<mrow>

<mfrac>

<mrow>

<msup>

</mrow>

</msup>

</mrow>

<mrow>

</mrow>

</mfrac>

</mrow>

<mfrac>

<mrow>

<msup>

</mrow>

</msup>

</mrow>

<mrow>

</mrow>

</mfrac>

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \;\left[{\frac {q^{m}-1}{q-1}},{\frac {q^{m}-1}{q-1}}-m;3,q\right]}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/557bfc965021eda639d5c7c17af8e1c4f063709f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:28.502ex; height:6.176ex;" alt="{\displaystyle \;\left[{\frac {q^{m}-1}{q-1}},{\frac {q^{m}-1}{q-1}}-m;3,q\right]}" loading="lazy">.</li>

<li>Der binäre <a href="Golay-Code" title="Golay-Code">Golay-Code</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {G}}_{23}}">

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {G}}_{23}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/5334cfeff3601d53e1e9d090885a7a28df1bee85.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.259ex; height:2.509ex;" alt="{\displaystyle {\mathcal {G}}_{23}}" loading="lazy"> mit Parametern <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle [23,12;7,2]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle [23,12;7,2]}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/71d94bdcff52e3ce3b8b9de229b3e9049c8ee73a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.37ex; height:2.843ex;" alt="{\displaystyle [23,12;7,2]}" loading="lazy">.</li>

<li>Der <a href="Tern%C3%A4rsystem" title="Ternärsystem">ternäre</a> <a href="Golay-Code" title="Golay-Code">Golay-Code</a> mit Parametern <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {G}}_{11}}">

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {G}}_{11}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/110736473b604d66a15ee646331fec637e51699c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.259ex; height:2.509ex;" alt="{\displaystyle {\mathcal {G}}_{11}}" loading="lazy"> mit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle [11,6;5,3]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle [11,6;5,3]}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0671c69acd4c93848c5fee58dfffe926fb045afd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.208ex; height:2.843ex;" alt="{\displaystyle [11,6;5,3]}" loading="lazy">.</li></ul>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0a07d98bb302f3856cbabc47b2b9016692e3f7bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.04ex; height:1.676ex;" alt="{\displaystyle m}" loading="lazy"> steht hierbei jeweils für eine positive natürliche Zahl <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m\in \mathbb {N} ^{+}}">

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m\in \mathbb {N} ^{+}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/d848dd10240db785375d53e65b5af43c8745a8b9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:8.07ex; height:2.509ex;" alt="{\displaystyle m\in \mathbb {N} ^{+}}" loading="lazy">.

Die Codes <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {C}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {C}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e7b3edab7022ca9e2976651bc59c489513ee9019.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.239ex; height:2.176ex;" alt="{\displaystyle {\mathcal {C}}}" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {D}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {D}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/3277962e1959c3241fb1b70c7f0ac6dcefebd966.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.792ex; height:2.176ex;" alt="{\displaystyle {\mathcal {D}}}" loading="lazy"> haben die gleichen Parameter und können somit bei gleicher Blocklänge <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> gleich viele Fehler korrigieren.

Die Umwandlung eines trivialen Codes in einen linearen Code mit denselben Parametern ist einfach: Falls der Code ein einziges Codewort enthält, so kann stattdessen auch der <a href="Nullvektor" title="Nullvektor">Nullvektor</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c_{0}=(0,\dots ,0)}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c_{0}=(0,\dots ,0)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/87c6d3b1583733887b835ccea13edb20a2c2eee2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.472ex; height:2.843ex;" alt="{\displaystyle c_{0}=(0,\dots ,0)}" loading="lazy"> als einziges Codewort dienen, und der entstandene Code ist linear. Der einzige verbleibende triviale Code ist derjenige, der sämtliche <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle q^{n}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle q^{n}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/31246d3db82f98a975bd9d9a5ea525679f89ff6e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.298ex; height:2.676ex;" alt="{\displaystyle q^{n}}" loading="lazy"> möglichen Wörter der gegebenen Blocklänge enthält. Dieser ist aber bereits linear.

Bei den restlichen Codes aus der Liste handelt es sich bereits um <a href="Linearer_Code" title="Linearer Code">lineare Codes</a>. Es gibt für jeden perfekten Code, der im Allgemeinen kein linearer Code ist, einen linearen Code mit den gleichen Parametern – sofern die Größe des Alphabetes eine Primzahlpotenz ist.

Es ist offen, ob, und für welche Parameter es nicht triviale perfekte Codes gibt, falls die Alphabetgröße keine Primzahlpotenz ist.

Für praktische Zwecke sind die trivialen Codes uninteressant, da entweder

<ul><li>keine Information übertragen werden kann oder</li>

<li>keine Fehler erkannt oder korrigiert werden können.</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Einzelnachweise">Einzelnachweise</h2></div>

<li id="cite_note-1"><a href="#cite_ref-1">↑</a> F.J. MacWilliams, N.J.A. Sloane: The Theory of Error-Correcting Codes. North-Holland, Amsterdam 1977

</li>

<li id="cite_note-2"><a href="#cite_ref-2">↑</a> Werner Lütkebohmert: Codierungstheorie. Vieweg, Braunschweig / Wiesbaden 2003

</li>

</ol></div><div><div class="zim-footer">

Dieser Artikel wurde von <a class="external text" title="Zuletzt bearbeitet am 2025-05-31" href="https://de.wikipedia.org/wiki/?title=Perfekter_Code&oldid=256518710">Wikipedia</a> herausgegeben. Der Text ist unter <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.de">Creative Commons Attribution-Share Alike 4.0</a> verfügbar, sofern nicht anders angegeben. Für die Mediendateien können zusätzliche Bedingungen gelten.

</div>

</div></div>

</div>

</main>

</div>

</body></html>